\chapter{查找}

\section{折半查找} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{Codex}[label=binary_search.c]
/** 数组元素的类型 */
typedef int elem_t;
/**
  * @brief 有序顺序表的折半查找算法.
  *
  * @param[in] a 存放数据元素的数组，已排好序
  * @param[in] n 数组的元素个数
  * @param[in] x 要查找的元素
  * @return 如果找到 x，则返回其下标。 如果找
  * 不到 x 且 x 小于 array 中的一个或多个元素，则为一个负数，该负数是大
  * 于 x 的第一个元素的索引的按位求补。 如果找不到 x 且 x 大于 array 中的
  * 任何元素，则为一个负数，该负数是（最后一个元素的索引加 1）的按位求补。 
  */
int binary_search(const elem_t a[], const int n, const elem_t x) {
    int left = 0, right = n -1, mid;
    while(left <= right) {
        mid = left + (right - left) / 2;
        if(x > a[mid]) {
            left = mid + 1;
        } else if(x < a[mid]) {
            right = mid - 1;
        } else {
            return mid;
        }
    }
    return -(left+1);
}
\end{Codex}


\section{哈希表} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\subsection{原理和实现}
\label{sec:hash-set}
哈希表处理冲突有两种方式，开地址法(Open Addressing)和闭地址法(Closed Addressing)。

闭地址法也即拉链法(Chaining)，每个哈希地址里不再是一个元素，而是链表的首地址。

开地址法有很多方案，有线性探测法(Linear Probing)、二次探测法(Quodratic Probing)和双散列法(Double Hashing)等。

下面是拉链法的C语言实现。

\subsubsection{代码}
\begin{Codex}[label=hash_set.hpp]
/** 元素的哈希函数  */
template<typename elem_t>
int elem_hash(const elem_t &e);

/** 元素的比较函数  */
template<typename elem_t>
bool operator==(const elem_t &e1, const elem_t &e2);

/** 哈希集合, elem_t 是元素的数据类型. */
template<typename elem_t>
class hash_set {
public:
    hash_set(int prime, int capacity);
    ~hash_set();
    bool find(const elem_t &elem); /** 查找某个元素是否存在. */
    bool insert(const elem_t &elem); /** 添加一个元素，如果已存在则添加失败. */
private:
    int prime; /** 哈希表取模的质数，也即哈希桶的个数，小于 capacity. */
    int capacity; /** 哈希表容量，一定要大于元素最大个数  */

    int *head/*[PRIME]*/; /** 首节点下标 */

    struct node_t {
        elem_t elem;
        int next;
        node_t():next(-1) {}
    } *node/*[HASH_SET_CAPACITY]*/; /** 静态链表 */

    int size; /** 实际元素个数 */
};

template<typename elem_t>
hash_set<elem_t>::hash_set(int prime, int capacity) {
    this->prime = prime;
    this->capacity = capacity;
    head = new int[prime];
    node = new node_t[capacity];
    fill(head, head + prime, -1);
    fill(node, node + capacity, node_t());
    size = 0;
}

template<typename elem_t>
hash_set<elem_t>::~hash_set() {
    this->prime = 0;
    this->capacity = 0;
    delete[] head;
    delete[] node;
    head = NULL;
    node = NULL;
    size = 0;
}

template<typename elem_t>
bool hash_set<elem_t>::find(const elem_t &elem) {
    for (int i = head[elem_hash(elem)]; i != -1; i = node[i].next)
        if (elem == node[i].elem) return true;

    return false;
}

template<typename elem_t>
bool hash_set<elem_t>::insert(const elem_t &elem) {
    const int hash_code = elem_hash(elem);

    for (int i = head[hash_code]; i != -1; i = node[i].next)
        if (elem == node[i].elem) return false; // 已经存在

    /* 不存在，则插入在首节点之前 */
    node[size].next = head[hash_code];
    node[size].elem = elem;
    head[hash_code] = size++;
    return true;
}
\end{Codex}


\subsection{Babelfish}


\subsubsection{描述}
You have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them.


\subsubsection{输入}
Input consists of up to 100,000 dictionary entries, followed by a blank line, followed by a message of up to 100,000 words. Each dictionary entry is a line containing an English word, followed by a space and a foreign language word. No foreign word appears more than once in the dictionary. The message is a sequence of words in the foreign language, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters.


\subsubsection{输出}
Output is the message translated to English, one word per line. Foreign words not in the dictionary should be translated as "eh".


\subsubsection{样例输入}
\begin{Code}
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay
\end{Code}


\subsubsection{样例输出}
\begin{Code}
cat
eh
loops
\end{Code}


\subsubsection{分析}
最简单的方法是，把输入的单词对，存放在一个数组，排好序，查找的时候每次进行二分查找。

更快的方法是，用HashMap。C++有\fn{map}，C++ 11以后有\fn{unordered_map}，比\fn{map}快。也可以自己实现哈希表。


\subsubsection{代码}
使用 \fn{map} 。

\begin{Codex}[label=babelfish_map.cpp]
/* POJ 2503 Babelfish , http://poj.org/problem?id=2503 */
#include <cstdio>
#include <map>
#include <string>
#include <cstring>

using namespace std;

/** 字符串最大长度 */
const int MAX_WORD_LEN = 10;

int main() {
    char line[MAX_WORD_LEN * 2 + 1];
    char s1[MAX_WORD_LEN + 1], s2[MAX_WORD_LEN + 1];
    map<string, string> dict;

    while (gets(line) && line[0] != 0) {
        sscanf(line, "%s %s", s1, s2);
        dict[s2] = s1;
    }

    while (gets(line)) {
        if (dict[line].length() == 0) puts("eh");
        else printf("%s\n", dict[line].c_str());
    }
    return 0;
}
\end{Codex}


自己实现哈希表。

\begin{Codex}[label=babelfish.cpp]
/* POJ 2503 Babelfish , http://poj.org/problem?id=2503 */
#include <cstring>

/** 单词最大长度. */
#define MAX_WORD_LEN   11

/** 词典中的一对. */
struct dict_pair_t {
    char english[MAX_WORD_LEN];
    char foreign[MAX_WORD_LEN];
};

/** 哈希表容量，一定要大于元素最大个数  */
#define HASH_SET_CAPACITY  100001
/** 哈希表取模的质数，也即哈希桶的个数，小于 HASH_SET_CAPACITY. */
#define PRIME  99997

int elem_hash(const dict_pair_t &e) {
    const char *str = e.foreign;
    unsigned int r = 0;
    int len = strlen(str);
    int i;

    for (i = 0; i < len; i++) {
        r = (r * 31 + str[i]) % PRIME;
    }
    return r % PRIME;
}

bool operator==(const dict_pair_t &e1, const dict_pair_t &e2) {
    return strcmp(e1.foreign, e2.foreign) == 0;
}

/* 等价于复制粘贴，这里为了节约篇幅，使用include，在OJ上提交时请用复制粘贴 */
#include "hash_set.hpp"  /* 见“查找->哈希表”这节 */

/* 跟find()略有不同，专为为本题定制 */
template<typename elem_t>
bool hash_set<elem_t>::get(elem_t &e) {
    for (int i = head[elem_hash(e)]; i != -1; i = node[i].next)
        if (e == node[i].elem) {
            // 多了一行代码，获取对应的 english
            strncpy(e.english, node[i].elem.english, MAX_WORD_LEN-1);
            return true;
        }

    return false;
}


int main() {
    char line[MAX_WORD_LEN * 2];
    hash_set<dict_pair_t> set(PRIME, HASH_SET_CAPACITY);
    dict_pair_t e;

    while (gets(line) && line[0] != 0) {
        sscanf(line, "%s %s", e.english, e.foreign);
        set.insert(e);
    }
    while (gets(e.foreign)) {
        if (set.get(e)) printf("%s\n", e.english);
        else printf("eh\n");
    }
    return 0;
}
\end{Codex}


\subsubsection{相关的题目}
与本题相同的题目：
\begindot
\item POJ 2503 Babelfish, \myurl{http://poj.org/problem?id=2503}
\myenddot

与本题相似的题目：
\begindot
\item  无
\myenddot
